package main

import (
	"errors"
	"fmt"
)

//PriorityQueue 优先级队列
type PriorityQueue struct {
	array    []int
	size     int
	maxFirst bool
}

//NewPriorityQueue 构建新优先级队列
func NewPriorityQueue(maxFirst bool) *PriorityQueue {
	return &PriorityQueue{
		array:    make([]int, 0),
		size:     0,
		maxFirst: maxFirst,
	}
}

//EnQueue 入队
func (q *PriorityQueue) EnQueue(num int) {
	q.array = append(q.array, num)
	q.size++
	//新元素加入后，进行上浮调整
	q.upAdjust()
}

//PrintElements 输出队列元素
func (q *PriorityQueue) PrintElements() {
	for _, v := range q.array {
		fmt.Printf("%v \n", v)
	}
}

func (q *PriorityQueue) upAdjust() {
	childIndex := q.size - 1
	parentIndex := (childIndex - 1) / 2
	//tmp保存当前叶子节点的值，用于最后赋值，没必要过程中交换值
	tmp := q.array[childIndex]
	for childIndex > 0 && q.upAdjustCompare(tmp, parentIndex) {
		q.array[childIndex] = q.array[parentIndex]
		childIndex = parentIndex
		parentIndex = parentIndex / 2
	}
	q.array[childIndex] = tmp
}

func (q *PriorityQueue) upAdjustCompare(tmp, pIndex int) bool {
	if q.maxFirst {
		return tmp > q.array[pIndex]
	}
	return tmp < q.array[pIndex]
}

func (q *PriorityQueue) downAdjust() {
	pIndex := 0
	//tmp保存当前父节点的值，用于最后赋值，没必要过程中交换值
	tmp := q.array[pIndex]
	cIndex := 1
	for cIndex < q.size {
		if cIndex+1 < q.size && q.downAdjustCompare1(cIndex) {
			cIndex++
		}
		if q.downAdjustCompare2(tmp, cIndex) {
			break
		}
		q.array[pIndex] = q.array[cIndex]
		pIndex = cIndex
		cIndex = 2*cIndex + 1
	}
	q.array[pIndex] = tmp
}

func (q *PriorityQueue) downAdjustCompare2(tmp, cIndex int) bool {
	if q.maxFirst {
		return tmp >= q.array[cIndex]
	}
	return tmp <= q.array[cIndex]
}

func (q *PriorityQueue) downAdjustCompare1(cIndex int) bool {
	if q.maxFirst {
		return q.array[cIndex+1] > q.array[cIndex]
	}
	return q.array[cIndex+1] < q.array[cIndex]
}

func (q *PriorityQueue) deQueue() (int, error) {
	if q.size <= 0 {
		return -1, errors.New("队列为空")
	}
	head := q.array[0]
	q.size--
	q.array[0] = q.array[q.size]
	q.downAdjust()
	return head, nil
}
